ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>NL (complexity)</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">NL (complexity)</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .unsolved{margin:0.5em 0 1em 1em;border:1px solid #a2a9b1;padding:0.35em 0.35em 0.35em 2.2em;background-color:var(--background-color-interactive-subtle);background-image:url("./mw/Question%2C_Web_Fundamentals.svg");background-position:top 50%left 0.35em;background-size:1.5em;background-repeat:no-repeat}@media(min-width:720px){.mw-parser-output .unsolved{clear:right;float:right;max-width:25%}}.mw-parser-output .unsolved-label{font-weight:bold}.mw-parser-output .unsolved-body{margin:0.35em;font-style:italic}.mw-parser-output .unsolved-more{font-size:smaller}

/* end https://en.wikipedia.org/ */

</style>

<div><span class="unsolved-label" id="unsolved-label-computer_science">Unsolved problem in computer science</span></div>

<mover>

</mover>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathsf {L{\overset {?}{=}}NL}}}</annotation>

</semantics>

</math></span><img src="./a631de5182ca00601efc30694e3425938dacedd7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.974ex; height:3.343ex;" alt="{\displaystyle {\mathsf {L{\overset {?}{=}}NL}}}" loading="lazy"></span>⁠</span></div>

<div class="unsolved-more"><a href="List_of_unsolved_problems_in_computer_science" title="List of unsolved problems in computer science">More unsolved problems in computer science</a></div>

</div>

<p>In <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, <b>NL</b> (<b>N</b>ondeterministic <b>L</b>ogarithmic-space) is the <a href="Complexity_class" title="Complexity class">complexity class</a> containing <a href="Decision_problem" title="Decision problem">decision problems</a> that can be solved by a <a href="Nondeterministic_Turing_machine" title="Nondeterministic Turing machine">nondeterministic Turing machine</a> using a <a href="Logarithm" title="Logarithm">logarithmic</a> amount of <a href="Memory_space_(computational_resource)" class="mw-redirect" title="Memory space (computational resource)">memory space</a>.

</p><p><b>NL</b> is a generalization of <b><a href="L_(complexity)" title="L (complexity)">L</a></b>, the class for logspace problems on a <a href="Deterministic_Turing_machine" class="mw-redirect" title="Deterministic Turing machine">deterministic Turing machine</a>. Since any deterministic Turing machine is also a <a href="Nondeterministic_Turing_machine" title="Nondeterministic Turing machine">nondeterministic Turing machine</a>, we have that <b>L</b> is contained in <b>NL</b>.

</p><p><b>NL</b> can be formally defined in terms of the computational resource <a href="Nondeterministic_space" class="mw-redirect" title="Nondeterministic space">nondeterministic space</a> (or NSPACE) as <b>NL</b> = <b>NSPACE</b>(log <i>n</i>).

</p><p>Important results in complexity theory allow us to relate this complexity class with other classes, telling us about the relative power of the resources involved. Results in the field of <a href="Algorithm" title="Algorithm">algorithms</a>, on the other hand, tell us which problems can be solved with this resource. Like much of complexity theory, many important questions about <b>NL</b> are still <a href="Open_problem" title="Open problem">open</a> (see <a href="Unsolved_problems_in_computer_science" class="mw-redirect" title="Unsolved problems in computer science">Unsolved problems in computer science</a>).

</p><p>Occasionally <b>NL</b> is referred to as <b>RL</b> due to its <a href="#Probabilistic_definition">probabilistic definition</a> below; however, this name is more frequently used to refer to <a href="RL_(complexity)" title="RL (complexity)">randomized logarithmic space</a>, which is not known to equal <b>NL</b>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2></div>

<p>There are several equivalent definitions of the <b>NL</b> class.

</p>

<div class="mw-heading mw-heading3"><h3 id="Standard_definition">Standard definition</h3></div>

<p><b>NL</b> is the complexity class of decision problems that can be solved by a nondeterministic Turing machine (NTM) using a logarithmic amount of memory space.

</p><p>In more detail, a language <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math></span><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"></span> is NL iff there exists a NTM <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math></span><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span> such that

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in L}</annotation>

</semantics>

</math></span><img src="./97fca945ad424639c27ec8dccaf96c0bda408d3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.753ex; height:2.176ex;" alt="{\displaystyle x\in L}" loading="lazy"></span>, then there exists at least one computational trace of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M(x)}</annotation>

</semantics>

</math></span><img src="./8d2fab18f2df9b523ef8b7b63a291317294fc708.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.581ex; height:2.843ex;" alt="{\displaystyle M(x)}" loading="lazy"></span> that results in the machine halting in an accepting state.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\not \in L}</annotation>

</semantics>

</math></span><img src="./7bad8cb4d1911470e72903bddf9106e678558c9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.753ex; height:2.676ex;" alt="{\displaystyle x\not \in L}" loading="lazy"></span>, then all computational traces of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M(x)}</annotation>

</semantics>

</math></span><img src="./8d2fab18f2df9b523ef8b7b63a291317294fc708.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.581ex; height:2.843ex;" alt="{\displaystyle M(x)}" loading="lazy"></span> results in the machine halting in an unaccepting state.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Probabilistic_definition">Probabilistic definition</h3></div>

<p>Suppose <i>C</i> is the <a href="Complexity_class" title="Complexity class">complexity class</a> of <a href="Decision_problems" class="mw-redirect" title="Decision problems">decision problems</a> solvable in logarithmithic space with <a href="Probabilistic_Turing_machine" title="Probabilistic Turing machine">probabilistic Turing machines</a> that never accept incorrectly but are allowed to reject incorrectly less than 1/3 of the time; this is called <i>one-sided error</i>. The constant 1/3 is arbitrary; any <i>x</i> with 0 ≤ <i>x</i> < 1/2 would suffice.

</p><p>It turns out that <i>C</i> = <b>NL</b>. Notice that <i>C</i>, unlike its deterministic counterpart <b><a href="L_(complexity)" title="L (complexity)">L</a></b>, is not limited to polynomial time, because although it has a polynomial number of configurations it can use randomness to escape an infinite loop. If we do limit it to polynomial time, we get the class <b><a href="RL_(complexity)" title="RL (complexity)">RL</a></b>, which is contained in but not known or believed to equal <b>NL</b>.

</p><p>There is a simple algorithm that establishes that <i>C</i> = <b>NL</b>. Clearly <i>C</i> is contained in <b>NL</b>, since:

</p>

<ul><li>If the string is not in the language, both reject along all computation paths.</li>

<li>If the string is in the language, an <b>NL</b> algorithm accepts along at least one computation path and a <i>C</i> algorithm accepts along at least two-thirds of its computation paths.</li></ul>

<p>To show that <b>NL</b> is contained in <i>C</i>, we simply take an <b>NL</b> algorithm and choose a random computation path of length <i>n</i>, and execute this 2<sup><i>n</i></sup> times. Because no computation path exceeds length <i>n</i>, and because there are 2<sup><i>n</i></sup> computation paths in all, we have a good chance of hitting the accepting one (bounded below by a constant).

</p><p>The only problem is that we don't have room in log space for a binary counter that goes up to 2<sup><i>n</i></sup>. To get around this we replace it with a <i>randomized</i> counter, which simply flips <i>n</i> coins and stops and rejects if they all land on heads. Since this event has probability 2<sup>−<i>n</i></sup>, we <a href="Expected_value" title="Expected value">expect</a> to take 2<sup><i>n</i></sup> steps on average before stopping. It only needs to keep a running total of the number of heads in a row it sees, which it can count in log space.

</p><p>Because of the <a href="Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem" title="Immerman–Szelepcsényi theorem">Immerman–Szelepcsényi theorem</a>, according to which NL is closed under complements, the one-sided error in these probabilistic computations can be replaced by zero-sided error. That is, these problems can be solved by probabilistic Turing machines that use logarithmic space and never make errors. The corresponding complexity class that also requires the machine to use only polynomial time is called ZPLP.

</p><p>Thus, when we only look at space, it seems that randomization and nondeterminism are equally powerful.

</p>

<div class="mw-heading mw-heading3"><h3 id="Certificate_definition">Certificate definition</h3></div>

<p><b>NL</b> can equivalently be characterised by <a href="Certificate_(complexity)" title="Certificate (complexity)">certificates</a>, analogous to classes such as <b><a href="NP_(complexity)" title="NP (complexity)">NP</a></b>. Let a <i>verifier</i> be a deterministic logarithmic-space bounded deterministic Turing machine that has an additional read-only read-once input tape (that is, the verifier may only move the read-head forwards, never backwards).

</p><p>A language <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math></span><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"></span> is in <b>NL</b> if and only if<sup id="cite_ref-:0_1-0" class="reference"><a href="#cite_note-:0-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: Definition 4.19">: Definition 4.19 </span></sup>

</p>

<ul><li>There exists a polynomial function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math></span><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span>.</li>

<li>There exists a verifier <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle TM}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle TM}</annotation>

</semantics>

</math></span><img src="./ea000afb5769206ddd5fd43f458430d04422ddeb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.078ex; height:2.176ex;" alt="{\displaystyle TM}" loading="lazy"></span>.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in L}</annotation>

</semantics>

</math></span><img src="./97fca945ad424639c27ec8dccaf96c0bda408d3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.753ex; height:2.176ex;" alt="{\displaystyle x\in L}" loading="lazy"></span> iff there exists a certificate <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math></span><img src="./c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"></span> with length <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |u|\leq p(|x|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |u|\leq p(|x|)}</annotation>

</semantics>

</math></span><img src="./89485d7d8368a1bde2d812c37c53ae98425d6c45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.324ex; height:2.843ex;" alt="{\displaystyle |u|\leq p(|x|)}" loading="lazy"></span>, such that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle TM(x,u)=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle TM(x,u)=1}</annotation>

</semantics>

</math></span><img src="./a3d9dbf20ef8331e931c0af68f34580242fbf5a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.842ex; height:2.843ex;" alt="{\displaystyle TM(x,u)=1}" loading="lazy"></span>.</li></ul>

<p>In words, it means that if a sentence is in the language, then there exists a polynomial-length proof that it is in the language. It does not say anything about the case where the sentence is <i>not</i> in the language, though by the Immerman–Szelepcsényi theorem, it is clear that there exists some verifier that can verify both <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in L}</annotation>

</semantics>

</math></span><img src="./97fca945ad424639c27ec8dccaf96c0bda408d3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.753ex; height:2.176ex;" alt="{\displaystyle x\in L}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\not \in L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\not \in L}</annotation>

</semantics>

</p><p>Note that the read-once condition is necessary. If the verifier can read forwards and backwards, this extends the class to the <b>NP</b> class.<sup id="cite_ref-:0_1-1" class="reference"><a href="#cite_note-:0-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: Exercise 4.7">: Exercise 4.7 </span></sup>

</p><p><a href="Cem_Say" title="Cem Say">Cem Say</a> and Abuzer Yakaryılmaz have proven that the deterministic logarithmic-space Turing machine in the statement above can be replaced by a bounded-error probabilistic constant-space Turing machine that is allowed to use only a constant number of random bits.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Descriptive_definition">Descriptive definition</h3></div>

<p>In <a href="Descriptive_complexity_theory" title="Descriptive complexity theory">descriptive complexity theory</a>, <b>NL</b> is defined as those languages expressible in <a href="First-order_logic" title="First-order logic">first-order logic</a> with an added <a href="Transitive_closure" title="Transitive closure">transitive closure</a> operator.

</p>

<div class="mw-heading mw-heading2"><h2 id="Closure_properties">Closure properties</h2></div>

<p>The class NL is closed under the operations complementation, union, and therefore intersection, <a href="Concatenation#Concatenation_of_sets_of_strings" title="Concatenation">concatenation</a>, and <a href="Kleene_star" title="Kleene star">Kleene star</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="NL-completeness">NL-completeness</h2></div>

<p>A problem is <b><a href="NL-complete" title="NL-complete">NL-complete</a></b> iff it is <b>NL</b>, and any problem in <b>NL</b> is <a href="Log-space_reduction" title="Log-space reduction">log-space reducible</a> to it.

</p><p>Problems that are known to be <b>NL</b>-complete including <a href="ST-connectivity" class="mw-redirect" title="ST-connectivity">ST-connectivity</a> and <a href="2-satisfiability" title="2-satisfiability">2-satisfiability</a>.

</p><p><a href="ST-connectivity" class="mw-redirect" title="ST-connectivity">ST-connectivity</a> asks, for nodes <i>S</i> and <i>T</i> in a <a href="Directed_graph" title="Directed graph">directed graph</a>, whether <i>T</i> is <a href="Reachability" title="Reachability">reachable</a> from <i>S</i>.

</p><p><a href="2-satisfiability" title="2-satisfiability">2-satisfiability</a> asks, given a <a href="Propositional_logic" title="Propositional logic">propositional</a> formula of which each clause is the <a href="Disjunction" class="mw-redirect" title="Disjunction">disjunction</a> of two literals, if there is a variable assignment that makes the formula true. An example instance, where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \neg }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \neg }</annotation>

</semantics>

</math></span><img src="./fa78fd02085d39aa58c9e47a6d4033ce41e02fad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.204ex; margin-bottom: -0.376ex; width:1.55ex; height:1.176ex;" alt="{\displaystyle \neg }" loading="lazy"></span> indicates <i>not</i>, might be:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1}\vee \neg x_{3})\wedge (\neg x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \neg x_{2})}</annotation>

</semantics>

</math></span><img src="./ee9a3913944f2e11cf894918942c7ae6b673b7f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:38.846ex; height:2.843ex;" alt="{\displaystyle (x_{1}\vee \neg x_{3})\wedge (\neg x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \neg x_{2})}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Containments">Containments</h2></div>

<p>It is known that <span style="font-family:sans-serif;">NL</span> is contained in <span style="font-family:sans-serif;"><a href="P_(complexity)" title="P (complexity)">P</a></span>, since there is a <a href="Polynomial-time_algorithm" class="mw-redirect" title="Polynomial-time algorithm">polynomial-time algorithm</a> for <a href="2-satisfiability" title="2-satisfiability">2-satisfiability</a>, but it is not known whether <span style="font-family:sans-serif;">NL = P</span> or whether <span style="font-family:sans-serif;">L = NL</span>. It is known that <span style="font-family:sans-serif;">NL = co-NL</span>, where <span style="font-family:sans-serif;">co-NL</span> is the class of languages whose <a href="Complement_(complexity)" title="Complement (complexity)">complements</a> are in <span style="font-family:sans-serif;">NL</span>. This result (the <a href="Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem" title="Immerman–Szelepcsényi theorem">Immerman–Szelepcsényi theorem</a>) was independently discovered by <a href="Neil_Immerman" title="Neil Immerman">Neil Immerman</a> and <a href="R%C3%B3bert_Szelepcs%C3%A9nyi" title="Róbert Szelepcsényi">Róbert Szelepcsényi</a> in 1987; they received the 1995 <a href="G%C3%B6del_Prize" title="Gödel Prize">Gödel Prize</a> for this work.

</p><p>In <a href="Circuit_complexity" title="Circuit complexity">circuit complexity</a>, <span style="font-family:sans-serif;">NL</span> can be placed within the <span style="font-family:sans-serif;"><a href="NC_(complexity)" title="NC (complexity)">NC</a></span> hierarchy. In Papadimitriou 1994, Theorem 16.1, we have:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathsf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}}}</annotation>

</semantics>

</math></span><img src="./07b83b7a32f54fa32cd69f797a2cb76979513eee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:21.831ex; height:2.509ex;" alt="{\displaystyle {\mathsf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}}}" loading="lazy"></span>.</dd></dl>

<p>More precisely, <span style="font-family:sans-serif;">NL</span> is contained in <span style="font-family:sans-serif;"><a href="AC_(complexity)" title="AC (complexity)">AC<sup>1</sup></a></span>. It is known that <span style="font-family:sans-serif;">NL</span> is equal to <span style="font-family:sans-serif;"><a href="ZPL_(complexity)" class="mw-redirect" title="ZPL (complexity)">ZPL</a></span>, the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error. It is not, however, known or believed to be equal to <span style="font-family:sans-serif;"><a href="RLP_(complexity)" class="mw-redirect" title="RLP (complexity)">RLP</a></span> or <span style="font-family:sans-serif;">ZPLP</span>, the polynomial-time restrictions of <span style="font-family:sans-serif;">RL</span> and <span style="font-family:sans-serif;">ZPL</span>, which some authors refer to as <span style="font-family:sans-serif;">RL</span> and <span style="font-family:sans-serif;">ZPL</span>.

</p><p>We can relate <span style="font-family:sans-serif;">NL</span> to deterministic space using <a href="Savitch's_theorem" title="Savitch's theorem">Savitch's theorem</a>, which tells us that any nondeterministic algorithm can be simulated by a deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that:

</p>

</mrow>

<msup>

</mrow>

</msup>

<mtext>equivalently, </mtext>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathsf {NL\subseteq SPACE}}(\log ^{2}n)\ \ \ \ {\text{equivalently, }}{\mathsf {NL\subseteq L}}^{2}.}</annotation>

</semantics>

</math></span><img src="./4d8c1e68172268f770af13314881e70f8c1bd2ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.677ex; height:3.176ex;" alt="{\displaystyle {\mathsf {NL\subseteq SPACE}}(\log ^{2}n)\ \ \ \ {\text{equivalently, }}{\mathsf {NL\subseteq L}}^{2}.}" loading="lazy"></span></dd></dl>

<p>This was the strongest deterministic-space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have <span style="font-family:sans-serif;"><a href="PSPACE" title="PSPACE">PSPACE</a> = <a href="NPSPACE" class="mw-redirect" title="NPSPACE">NPSPACE</a></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAroraBarak2009" class="citation book cs1"><a href="Sanjeev_Arora" title="Sanjeev Arora">Arora, Sanjeev</a>; <a href="Boaz_Barak" title="Boaz Barak">Barak, Boaz</a> (2009). <a rel="nofollow" class="external text" href="http://www.cs.princeton.edu/theory/complexity/"><i>Complexity Theory: A Modern Approach</i></a>. Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-42426-4</bdi>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">A. C. Cem Say, Abuzer Yakaryılmaz, "Finite state verifiers with constant randomness," <i>Logical Methods in Computer Science</i>, Vol. 10(3:6)2014, pp. 1-17.</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><i><a href="Complexity_Zoo" class="mw-redirect" title="Complexity Zoo">Complexity Zoo</a></i>: <a rel="nofollow" class="external text" href="https://complexityzoo.net/Complexity_Zoo:N#nl">NL</a></li>

<li><cite id="CITEREFPapadimitriou1994" class="citation book cs1">Papadimitriou, C. (1994). "Chapter 16: Logarithmic Space". <i>Computational Complexity</i>. Addison-Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-53082-1</bdi>.</cite></li>

<li><cite id="CITEREFMichael_Sipser1997" class="citation book cs1"><a href="Michael_Sipser" title="Michael Sipser">Michael Sipser</a> (27 June 1997). "Sections 8.4–8.6: The Classes L and NL, NL-completeness, NL equals coNL". <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoth00sips/page/294"><i>Introduction to the Theory of Computation</i></a></span>. PWS Publishing. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoth00sips/page/294">294–302</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-534-94728-X</bdi>.</cite></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20160303183247/http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l7.ps">Introduction to Complexity Theory: Lecture 7</a>. Oded Goldreich. Proposition 6.1. Our <i>C</i> is what Goldreich calls badRSPACE(log n).</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Complexity_classes148" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Complexity_classes148" style="font-size:114%;margin:0 4em"><a href="Complexity_class" title="Complexity class">Complexity classes</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Considered feasible</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="DLOGTIME" title="DLOGTIME">DLOGTIME</a></li>

<li>

<ul><li><a href="NL-complete" title="NL-complete">NL-complete</a></li></ul></li>

<ul><li><a href="P-complete" title="P-complete">P-complete</a></li></ul></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Suspected infeasible</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="NP-completeness" title="NP-completeness">NP-complete</a></li>

<li><a href="Co-NP-complete" title="Co-NP-complete">co-NP-complete</a></li></ul></li>

<ul><li><a href="%E2%99%AFP-complete" title="♯P-complete">#P-complete</a></li></ul></li>

<li><a href="PSPACE" title="PSPACE">PSPACE</a>

<ul><li><a href="PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Considered infeasible</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="EXPTIME" title="EXPTIME">EXPTIME</a></li>

<li><a href="NEXPTIME" title="NEXPTIME">NEXPTIME</a></li>

<li><a href="EXPSPACE" title="EXPSPACE">EXPSPACE</a></li>

<li><a href="2-EXPTIME" title="2-EXPTIME">2-EXPTIME</a></li>

<li><a href="ELEMENTARY" title="ELEMENTARY">ELEMENTARY</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Class hierarchies</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Polynomial_hierarchy" title="Polynomial hierarchy">Polynomial hierarchy</a></li>

<li><a href="Exponential_hierarchy" title="Exponential hierarchy">Exponential hierarchy</a></li>

<li><a href="Grzegorczyk_hierarchy" title="Grzegorczyk hierarchy">Grzegorczyk hierarchy</a></li>

<li><a href="Arithmetical_hierarchy" title="Arithmetical hierarchy">Arithmetical hierarchy</a></li>

<li><a href="Boolean_hierarchy" title="Boolean hierarchy">Boolean hierarchy</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Families of classes</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="DTIME" title="DTIME">DTIME</a></li>

<li><a href="NTIME" title="NTIME">NTIME</a></li>

<li><a href="DSPACE" title="DSPACE">DSPACE</a></li>

<li><a href="NSPACE" title="NSPACE">NSPACE</a></li>

<li><a href="Probabilistically_checkable_proof" title="Probabilistically checkable proof">Probabilistically checkable proof</a></li>

<li><a href="Interactive_proof_system" title="Interactive proof system">Interactive proof system</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><a href="List_of_complexity_classes" title="List of complexity classes">List of complexity classes</a></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-12" href="https://en.wikipedia.org/wiki/?title=NL_(complexity)&oldid=1289991805">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>